/**
 * 一，数组的定义和特点
 * 
 * 1. 定义：数组是有限个相同类型的变量所组成的有序集合。
 * 
 * 2. 特点：
 *  (1) 数组是最简单、最为常用的数据结构。
 *          
 *  (2) 数组中每一个元素有着自己的下标，这个下标从0开始，一直到数组长度-1。
 *          
 *  (3) 数组是在内存中顺序存储。
 * 
 *  */ 


// 二，实现数组的操作

// 2.1 创建一个空数组
function MyArray() {
    const array = new Array();

    return array;
}

/**
 * 
 * 2.2数组插入方法
 * @param 
 * index 插入的位置
 * element 插入的元素
 * 数组扩容暂时不做（超数组暂不考虑）
 * 
 * **/
Array.prototype.insertElement = function insertElement(index, element) {
    const array = this;

    if(index < 0 || index > this.length) {
        alert("超出数组实际元素范围");
        return;
    }
    // 尾部插入
    if(index === this.length) {
        array[this.length] = element;
    } else {
        // 中间插入
        for(let i=this.length-1; i>=index; i--) {
            array[i+1] = array[i];
        }
        // 腾出的位置放入新元素
        array[index] = element;
    }
    
    return array;
}

/**
 * 
 * 2.3 数组删除方法
 * @param
 * index 删除的位置
 * 
 * **/
Array.prototype.deleteElement = function deleteElement(index) {
    const array = this;

    if(index < 0 || index >= array.length) {
        alert('超出数组实际元素范围');
        return;
    }
    
    const deletedElement = array[index];
    for(let i=index; i<array.length-1; i++) {
        array[i] = array[i+1];
    }
    
    array.length--;

    return deletedElement;
}

// 2.4 输出元素
Array.prototype.outputArray = function outputArray() {
    for(let i=0; i<this.length; i++) {
        console.log(i);
    }
}

//2.5 操作demo
const myArray = MyArray();
console.log(myArray, 1);
console.log(myArray.insertElement(0, 1));
console.log(myArray.insertElement(1, 2));
console.log(myArray.insertElement(1, 3));
console.log(myArray.insertElement(3, 5));
console.log(myArray.insertElement(0, 10));
console.log(myArray, 2);
console.log(myArray.deleteElement(0));
console.log(myArray.deleteElement(0));
console.log(myArray.deleteElement(2));
console.log(myArray, 3);
console.log(myArray.outputArray(), 4);


/**
 * 三，链表的定义，单向链表和双向链表的区别
 * 
 * 1. 定义：链表是一种在物理上非连续、非顺序的数据结构，由若干节点所组成。
 * 
 * 2. 单向链表：单向链表的每一个节点包含两部分，一部分是存放数据的变量data, 另一部分是指向下一个节点的指针next
 * 
 * 3. 双向链表：它的每一个节点除了拥有data和next指针，还拥有指向前置节点的prev指针。
 * 
 * 4. 单向链表和双向链表的区别：双向链表既可以找到该节点的下一个节点，也可以找到该节点的上一个节点。
 * 
 *  
 * **/


 // 四，实现链表的操作
 (function myLinkList(){
     // 头节点指针
     let head;
     // 尾节点指针
     let last;
     // 链表实际长度
     let size = 0;

     // 链表插入元素
     function insertNode(data, index) {
        if (index < 0 || index > size) {
            alert('超出链表节点范围');
            return;
        }

        const insertedNode = data;
        if(size === 0) {
            // 空链表
            head = insertedNode;
            last = insertedNode;
        } else if(index === 0) {
            // 插入头部
            insertedNode.next = head;
            head = insertedNode;
        } else if(size == index) {
            // 插入尾部
            last.next = insertedNode;
            last = insertedNode;
        } else {
            // 插入中间
            const prevNode = get(index - 1);
            insertedNode.next = prevNode.next;
            prevNode.next = insertedNode;
        }

        size++;
     }

     // 链表删除元素
     function removeNode(index) {
        if(index < 0 || index >= size) {
            alert('超出链表节点范围');
            return;
        }

        const removedNode = null;
        if(index == 0) {
            // 删除头节点
            removedNode = head;
            head = head.next;
        } else if (index === size - 1) {
            // 删除尾节点
            const prevNode = get(index - 1);
            removedNode = prevNode.next;
            last = prevNode;
        } else {
            // 删除中间节点
            const prevNode = get(index - 1);
            const nextNode = prevNode.next.next;
            removedNode = prevNode.next;
            prevNode.next = nextNode; 
        }

        size--;

        return removedNode;
     }

     // 链表查找元素
     function getNode(index) {
        if (index < 0 || index >= size) {
            alert('超出链表节点范围');
            return;
        }

        const temp = head;
        for(var i=0; i<index; i++) {
            temp = temp.next;
        }

        return temp;
     }

     // 输出链表
     function outputLinkList() {
        const temp = head;
        while(temp !== null) {
            console.log(temp.data);
            temp = temp.next;
        }
     }
 })();


 /**
  * 
  * 五. 数据存储的物理结构和逻辑结构定义，栈和队列的定义。
  * 
  * 1.数据存储的物理结构：内存中实实在在的存储结构。
  * 
  * 2.数据存储的逻辑结构：逻辑结构是抽象的概念。
  * 
  * 3.栈：是一种线性数据结构，先入后出。最早进入的元素存放的位置叫做栈底，最后进入的元素存放的位置叫做栈顶。
  * 
  * 4.队列：是一种线性数据结构，先入先出。队列的出口端叫做队头，队列的入口端叫做队尾。
  * 
  * **/

  /**
   * 
   * 六. 散列表的定义，哈希冲突的定义和如何解决哈希冲突的问题
   * 
   * 1.散列表的定义：散列表即哈希表，这种数据结构提供了键和值的映射关系。只要给出一个key,就可以高效查到它所匹配的value。
   * 
   * 2.哈希冲突的定义：不同的key通过哈希函数获得的下标有可能是相同的，这种情况就叫做哈希冲突。
   * 
   * 3.解决哈希冲突的方法主要有两种：一种是开放寻址法，一种是链表法。
   * 
   * **/

   /**
    * 
    * 七. 什么时候需要散列表进行扩展，散列表扩容的操作具体做的事情？
    * 
    * 1.当经过多次元素插入，散列表达到一定饱和度时，key映射位置发生冲突的概率会逐渐提高。
    * 这样一来，大量元素拥挤在相同的数组下标位置，形成很长的链表，对后续插入操作和查询操作的性能都有很大的影响。
    * 这时，散列表就需要扩展它的长度，也就是进行扩容。
    * 
    * 2.散列表扩容的操作具体做的事情：
    * (1)扩容：创建一个新的Entry空数组，长度是原数组的2倍。
    * (2)重新Hash：遍历原Entry数组，把所有的Entry重新Hash到新数组中。
    * 
    * **/